package com.agile.leetcode.node.reserveNode;

/**
 * 反转链表
 *
 * @Author KD
 * @Date 2021/2/26 13:46
 */
public class ReserveNode {
    public static void main(String[] args) {
        Node node5 = new Node(5, null);
        Node node4 = new Node(4, node5);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node node1 = new Node(1, node2);
        ReserveNode reserveNode = new ReserveNode();
        Node node = reserveNode.reserveNode(node1);
        System.out.println(node);
        // 反转回来
        Node node6 = reserveNode.reserveNode_1(node);
        System.out.println(node6);
        System.out.println(reserveNode.reserveNode_2(node6));

        System.out.println(reserveNode.reserveNode_4(node6));
    }

    /**
     * 翻转链表
     *
     * @param root
     * @return
     */
    public Node reserveNode(Node root) {
        // 定义头指针
        Node pre = null;
        // 定义辅助指针
        Node cur = root;
        while (cur != null) {
            // 拿到下一个
            Node next = cur.next;
            // 将下一个变成pre
            cur.next = pre;
            // pre进行赋值
            pre = cur;
            // 指针循环
            cur = next;
        }
        return pre;
    }

    /**
     * 翻转链表的复习
     *
     * @param root
     * @return
     */
    public Node reserveNode_1(Node root) {
        // 定义辅助链表
        Node dummy = new Node(0, null);
        Node current = dummy;
        // 遍历
        while (root != null) {
            // 拿到当前节点
            int val = root.value;
            // 拿到dummy的下一结点
            Node next = current.next;
            Node newNode = new Node(val, next);
            // 加入dummy节点
            current.next = newNode;
            // 指针后移
            root = root.next;
        }
        return dummy.next;
    }

    /**
     * 翻转链表
     *
     * @param root
     * @return
     */
    public Node reserveNode_2(Node root) {
        // 定义雅节点
        Node dummy = new Node(0, null);
        // 定义辅助节点
        Node current = dummy;
        while (root != null) {
            // 拿到当前节点
            int value = root.value;
            // 拿到辅助节点的下一结点
            Node next = current.next;
            // 定义新节点
            Node newNode = new Node(value, next);
            // 添加
            current.next = newNode;
            root = root.next;
        }
        return dummy.next;
    }

    public Node reserveNode_3(Node root) {
        // 创建dummy
        Node dummy = new Node(0, null);
        Node current = dummy;
        while (root != null) {
            // 拿到当前
            int value = root.value;
            // 拿到下个节点
            Node next = current.next;
            // 创建新节点
            Node newNode = new Node(value, next);
            current.next = newNode;
            root = root.next;
        }
        return dummy.next;
    }

    public Node reserveNode_4(Node root) {
        if (root == null || root.next == null) {
            return root;
        }
        Node rev = reserveNode_4(root.next);
        root.next.next = root;
        root.next = null;
        return rev;
    }
}

class Node {
    int value;
    Node next;

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", next=" + next +
                '}';
    }

}
